package org.algorithm.biubiu.wheel_1.回溯算法;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * <p>
 * 你可以按 任何顺序 返回答案。
 * <p>
 * <p>
 * 77. 组合
 * https://leetcode-cn.com/problems/combinations/
 */
public class $4月20日$组合 {


    class Solution {

        List<List<Integer>> res = new ArrayList();
        int k;
        int n;
        public List<List<Integer>> combine(int n, int k) {
            if(k>n){
                return res;
            }
            this.k = k;
            this.n=n;
            backTrack(1);
            return res;
        }


        List<Integer> cur = new ArrayList();
        public void backTrack(int index){
            if(cur.size()==k){
                res.add(new ArrayList(cur));
                return;
            }

            for(int i = index;i<=n;i++){

                cur.add(i);
                backTrack(i+1);
                cur.remove(cur.size()-1);
            }
        }
    }
}
